#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType *elem;//整型指针
    int TableLen;
} SSTable;

void ST_Init(SSTable &ST, int len) {
    ST.TableLen = len + 1;//实际申请11个元素的空间
    ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);
    int i;
    srand(time(NULL));
    for (i = 0; i < ST.TableLen; i++) {
        ST.elem[i] = rand() % 100;//随机了11个数，但是第一个元素是没有用到的
    }
}

void ST_print(SSTable ST) {
    for (int i = 0; i < ST.TableLen; i++) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}

void swap(ElemType &a, ElemType &b) {
    ElemType tmp;
    tmp = a;
    a = b;
    b = tmp;
}

// 64 94 95 79 69 84 18 22 12 78
// 12 64 94 95 79 69 84 18 22 78
void BubbleSort(ElemType A[], int n) {
    int i, j;
    bool flag;
    for (i = 0; i < n - 1; i++)//i最多访问到8
    {
        flag = false;
        for (j = n - 1; j > i; j--)//把最小值就放在最前面
        {
            if (A[j - 1] > A[j]) {
                swap(A[j - 1], A[j]);
                flag = true;
            }
        }
        if (false == flag)
            return;
    }
}

void BubbleSort1(ElemType A[], int n) {
    int i, j, flag;
    for (i = 0; i < n - 1; i++)//i是控制有多少个有序了
    {
        flag = 0;
        for (j = n - 1; j > i; j--)//内层控制比较，交换
        {
            if (A[j - 1] > A[j]) {
                swap(A[j - 1], A[j]);
                flag = 1;
            }
        }
        if (0 == flag) {
            break;
        }
    }
}
// 64 94 95 79 69 84 18 22 12 78
//比64小的放在左边，比64大的放在右边 快速排序 王道书写法
//int Partition(ElemType A[],int low,int high)
//{
//	ElemType pivot=A[low];
//	while(low<high)
//	{
//		while(low<high&&A[high]>=pivot)
//			--high;
//		A[low]=A[high];
//		while(low<high&&A[low]<=pivot)
//			++low;
//		A[high]=A[low];
//	}
//	A[low]=pivot;
//	return low;
//}

//快速排序 龙哥写法 更简洁
int Partition(int *arr, int left, int right) {
    int k, i;
    for (k = i = left; i < right; i++) {
        if (arr[i] < arr[right]) {
            swap(arr[i], arr[k]);
            k++;
        }
    }
    swap(arr[k], arr[right]);
    return k;
}

//递归实现
void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high);//分割点左边的元素都比分割点要小，右边的比分割点大
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

//插入排序，从小到大排序，升序
void InsertSort(ElemType A[], int n) {
    int i, j;
    //24 66 94  2 15 74 28 51 22 18  2
    for (i = 2; i <= n; i++)//第零个元素是哨兵，从第二个元素开始拿，往前面插入
    {
        if (A[i] < A[i - 1]) {
            A[0] = A[i];//放到暂存位置，A[0]即是暂存，也是哨兵
            for (j = i - 1; A[0] < A[j]; --j)//移动元素，内层循环控制有序序列中的每一个元素和要插入的元素比较
                A[j + 1] = A[j];
            A[j + 1] = A[0];//把暂存元素插入到对应位置
        }
    }
}

//折半查找 插入排序
void MidInsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        A[0] = A[i];
        low = 1;
        high = i - 1;
        while (low <= high)//先通过二分查找找到待插入位置
        {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}

//希尔排序
//多轮插入排序，考的概率很低，因为编写起来复杂，同时效率并不如快排，堆排
void ShellSort(ElemType A[], int n) {
    int dk, i, j;
    // 73 29 74 51 29 90 37 48 72 54 83
    for (dk = n / 2; dk >= 1; dk = dk / 2)//步长变化
    {
        for (i = dk + 1; i <= n; ++i)//以dk为步长进行插入排序
        {
            if (A[i] < A[i - dk]) {
                A[0] = A[i];
                for (j = i - dk; j > 0 && A[0] < A[j]; j = j - dk)
                    A[j + dk] = A[j];
                A[j + dk] = A[0];
            }
        }
    }
}

int main() {
    SSTable ST;
    ST_Init(ST, 10);//实际申请了11个元素空间
    ST_print(ST);
    InsertSort(ST.elem, 10);
    //MidInsertSort(ST.elem,10);
    //ShellSort(ST.elem,10);
    ST_print(ST);
    system("pause");
}
